package base.sort.normal;

import base.sort.IMutableSorter;
import base.sort.Swapper;

public class SelectionSort implements IMutableSorter {

    @Override
    public void sort(int[] A) {
        for (int i = A.length - 1; i >= 0; i--) {
            // 找到最大元素下标
            int j = maxIndexStable(A, 0, i + 1);
            Swapper.swap(A, i, j);
        }
    }

    /**
     * 存在同值稳定性问题即相同大小交换了位置
     * 3 3 1 1
     *     3 3
     */
    static private int maxIndex(int[] A, int i, int j) {
        int max = Integer.MIN_VALUE;

        int maxIndex = i;
        // 从左边开始找最大值
        for (int k = 0; k < j; k++) {
            if(max < A[k]) {
                max = A[k];
                maxIndex = k;
            }
        }
        return maxIndex;
    }

    /**
     * 解决同值稳定性问题，反过来找
     */
    static private int maxIndexStable(int[] A, int i, int j) {
        int max = Integer.MIN_VALUE;
        int maxIndex = j-1;
        // 从右边开始找
        for (int k = j-1; k >= i; k--) {
            if(max < A[k]) {
                max = A[k];
                maxIndex = k;
            }
        }
        return maxIndex;
    }
}
